package ACWing.mathematicalknowledge.快速幂;
//875. 快速幂

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2023/1/11 20:05
 */
public class ASimpleMathProblem {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while (n-->0){
            int a=sc.nextInt();
            int k=sc.nextInt();
            int p=sc.nextInt();
            System.out.println(qmi(a, k, p));
        }
    }
    public static int qmi(int a,int k,int p){
        int res=1;
        while (k>0){
            if((k&1)==1){
                res= (int)((long)res*a%p);
            }
            k=k>>1;
            a = (int)((long)a*a%p);
        }
        return res;
    }
}
